SP694 DISUBSTR - Distinct Substrings

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »

SP1811 LCS - Longest Common Substring

一道后缀自动机的板题。

我们从根结点开始匹配,如果有转移就将cnt++cnt++

不然就顺着后缀链接向上跳,直到找到有转移的点,用 MaxlenMaxlen 继续匹配。(后缀链接一定是它的子串,也能被匹配)。

阅读全文 »

SP1812 LCS2 - Longest Common Substring II

我们可以思考一下如何用SAM\text{SAM}求两个串的最长公共子串点这里

多个字符串匹配也很简单,对于每个节点记录每个字符串能匹配的最大值的最小值。

求最大值就是求两个串的最长公共子串,只不过需要给父节点更新,每次取最小值就得到答案。

阅读全文 »

P2408 不同子串个数

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »

SP8222 NSUBSTR - Substrings

不难发现到f[i]f[i]就是长度为 ii 子串的 endpos|endpos| 的最大值。

根据一个性质后缀自动机的一个点的 endposendpos 被他的后继分为了很多部分,所以我们可以用parent树dp\text{parent树dp},处理出它的endpos|endpos|

接着是统计答案,显然我们可以用线段树覆盖。

阅读全文 »

P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 dpdp 蒟蒻都能一眼看出 dpdp 式:

sumsumcc 的前缀和,则有

dp[i]=min{dp[j]+((ij1)+(sum[i]sum[j])L)2}  (0j<i)dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)

阅读全文 »

CF487B Strip

一道并不难的 dpdp 题。转移式很好列:

dp[i]=min{dp[j]+1}    (0jil &&max(j+1,i)min(j+1,i)<=s)dp[i]=min\{ dp[j]+1 \} ~~~~ (0 \le j \le i - l~\&\&max(j+1,i)-min(j+1,i)<=s)

阅读全文 »